P3195 [HNOI2008]玩具装箱TOY

这道题像我这样的 $dp$ 蒟蒻都能一眼看出 $dp$ 式：

设 $sum$ 为 $c$ 的前缀和，则有

$dp[i]=min\{ dp[j]+((i-j-1)+(sum[i]-sum[j])-L)^2 \} ~~ (0 \le j < i)$

就可以$\Theta(n^2)$解决了 ，开O2骗了70分。

考虑优化，令$s_i=sum[i]+i$,则有：

$dp[i]=min\{ dp[j] + (s_i-s_j-1-L)^2 \} ~~~~ (0 \le j < i)$

将 $s_i-1-L$ 看作一个整体拆开平方（它们与决策点 $j$ 无关），得到:

$dp[i]=min\{ dp[j] + {s_j}^2 - 2 \times s_j \times (s_i-L-1) \}+(s_i-L-1)^2 ~~~~ (0 \le j < 0)$

$dp[i]=min\{ dp[j] + {s_j}^2 - 2s_is_j + 2Ls_j + 2s_j \}+(s_i-L-1)^2 ~~~~ (0 \le j < 0)$

然后是斜优的套路，设两个决策点 $j,k (j<k)$ 且 $j$ 优于 $k$。即:

$dp[j] + {s_j}^2 - 2s_is_j + 2Ls_j + 2s_j<dp[k] + {s_k}^2 - 2s_is_k + 2Ls_k + 2s_k$

$(dp[j]+{s_j}^2)-(dp[k]+{s_k}^2)+2L(s_j-s_k)+2(s_j-s_k)<2s_i(s_j-s_k)$

注意$s_j<s_k$ ， 移项变号：

$\frac{(dp[j]+{s_j}^2)-(dp[k]+{s_k}^2)+2(L+1)(s_j-s_k)}{s_j-s_k}>2s_i$

$\frac{(dp[j]+{s_j}^2+2s_j(L+1))-(dp[k]+{s_k}^2+2s_k(L+1))}{s_j-s_k}>2s_i$

现在就可以维护一个下凸包解决，时间复杂度$\Theta(n)$。

#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long

const int MAXN = 50000;
int n , l , c[ MAXN + 5 ] , Head = 1 , Tail = 0 , Que[ MAXN + 5 ];
LL sum[ MAXN + 5 ] , dp[ MAXN + 5 ];

LL Calc( int i ) {
    return sum[ i ] + i;
}
double Slope( int u , int v ) {
    return ( ( dp[ u ] + Calc( u ) * Calc( u ) + 2 * Calc( u ) * ( l + 1 ) ) - ( dp[ v ] + Calc( v ) * Calc( v )+ 2 * Calc( v ) * ( l + 1 ) ) ) / ( Calc( u ) - Calc( v ) );
}

int main( ) {
    scanf("%d %d",&n,&l);
    for( int i = 1 ; i <= n ; i ++ )
        scanf("%d",&c[ i ]) , sum[ i ] = sum[ i - 1 ] + c[ i ];
    
    Que[ ++ Tail ] = 0;
    for( int i = 1 ; i <= n ; i ++ ) {
        while( Head < Tail && Slope( Que[ Head ] , Que[ Head + 1 ] ) < 2 * Calc( i ) ) Head ++;

        dp[ i ] = dp[ Que[ Head ] ] + ( Calc( i ) - Calc( Que[ Head ] ) - 1 - l ) * ( Calc( i ) - Calc( Que[ Head ] ) - 1 - l );
        while( Head < Tail && Slope( Que[ Tail - 1 ] , Que[ Tail ] ) > Slope( Que[ Tail - 1 ] , i ) ) Tail --;
        Que[ ++ Tail ] = i;
    }

    printf("%lld",dp[ n ]);
    return 0;
}